#include <iostream>
#include <set>
#include <map>
#include <list>
#include <initializer_list>

using namespace std;

struct Vertex
{
	size_t _id = 0;
	char _data = 0;
	std::set<size_t> _edges;

	void show(std::ostream& os) const;
};

struct DFSTree;
struct DFSForest;
struct Graph
{
	std::map<size_t, Vertex> _vert;

	void addVertex(size_t id, char data);
	void addEdge(size_t id1, size_t id2);
	void addUEdge(size_t id1, size_t id2);
	bool calcDFS(DFSForest& forest);
	void visitDFS(Vertex& vert, DFSForest& forest, DFSTree*& pTree, DFSTree* pTreeParent = NULL);
	void show(std::ostream& os) const;
};

struct DFSForest
{
	Graph* _pOwner = NULL;
	size_t _time = 0;
	std::map<size_t, DFSTree*> _findMap;
	std::map<size_t, DFSTree> _forest;

	DFSForest() {}
	DFSForest(std::initializer_list<size_t> il);
	void show(std::ostream& os) const;
};

struct DFSTree
{
	DFSForest* _pOwner = NULL;
	DFSTree* _pParent = NULL;
	size_t _id = 0;
	size_t _begTime = 0;
	size_t _endTime = 0;
	std::map<size_t, DFSTree> _cld;

	DFSTree() {}
	DFSTree(size_t id) { _id = id; }
	void show(std::ostream& os) const;
};

int main()
{
	Graph graph;
	graph.addVertex(1, 'u');
	graph.addVertex(2, 'v');
	graph.addVertex(3, 'w');
	graph.addVertex(4, 'x');
	graph.addVertex(5, 'y');
	graph.addVertex(6, 'z');
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(2, 5);
	graph.addEdge(3, 5);
	graph.addEdge(3, 6);
	graph.addEdge(4, 2);
	graph.addEdge(5, 4);
	graph.addEdge(6, 6);
	graph.show(cout);

	DFSForest forest;
	graph.calcDFS(forest);
	forest.show(cout);

	return 0;
}

void Vertex::show(std::ostream& os) const
{
	os << "[" << _id << "]" << _data << ",{";
	bool first = true;
	for (auto i : _edges)
	{
		if (first) first = false;
		else os << ",";

		os << i;
	}
	os << "}";
}

void Graph::addVertex(size_t id, char data)
{
	Vertex& v = _vert[id];
	if (v._id)
		return;

	v._id = id;
	v._data = data;
}

void Graph::addEdge(size_t id1, size_t id2)
{
	auto it1 = _vert.find(id1);
	if (it1 == _vert.end())
		return;

	auto it2 = _vert.find(id2);
	if (it2 == _vert.end())
		return;

	it1->second._edges.insert(id2);
}

void Graph::addUEdge(size_t id1, size_t id2)
{
	auto it1 = _vert.find(id1);
	if (it1 == _vert.end())
		return;

	auto it2 = _vert.find(id2);
	if (it2 == _vert.end())
		return;

	it1->second._edges.insert(id2);
	it2->second._edges.insert(id1);
}

bool Graph::calcDFS(DFSForest& forest)
{
	forest._pOwner = this;
	forest._time = 0;
	forest._findMap.clear();
	forest._forest.clear();

	for (auto& [id, vert] : _vert)
	{
		if (forest._findMap.find(id) == forest._findMap.end())
			visitDFS(vert, forest, forest._findMap[id]);
	}

	return true;
}

void Graph::visitDFS(Vertex& vert, DFSForest& forest, DFSTree*& pTree, DFSTree* pTreeParent)
{
	pTree = pTreeParent ? &pTreeParent->_cld[vert._id] : & forest._forest[vert._id];
	pTree->_pOwner = &forest;
	pTree->_pParent = pTreeParent;
	pTree->_id = vert._id;
	pTree->_begTime = ++forest._time;
	for (auto id : vert._edges)
	{
		if (forest._findMap.find(id) == forest._findMap.end())
			 visitDFS(_vert[id], forest, forest._findMap[id], pTree);
	}

	pTree->_endTime = ++forest._time;
}

void Graph::show(std::ostream& os) const
{
	for (auto& pr : _vert)
	{
		pr.second.show(os);
		os << std::endl;
	}
}

DFSForest::DFSForest(std::initializer_list<size_t> il)
{
	for (auto id : il)
	{
		if (!id)
			continue;

		DFSTree& tree = _forest[id];
		tree._id = id;
	}
}

void DFSForest::show(std::ostream& os) const
{
	if (!_pOwner)
	{
		os << "Error";
		return;
	}

	os << "time=" << _time << ",forest={";
	bool first = true;
	for (auto& [id, vert] : _forest)
	{
		if (first) first = false;
		else os << ",";

		vert.show(os);
	}

	os << "}";
}

void DFSTree::show(std::ostream& os) const
{
	if (!_pOwner)
	{
		os << "Error";
		return;
	}

	os << "[" << _id << "]";
	auto it = _pOwner->_pOwner->_vert.find(_id);
	if (it == _pOwner->_pOwner->_vert.end())
		os << "Null";
	else
		os << it->second._data;

	os << ",time=" << _begTime << "-" << _endTime;
	if (_cld.empty())
		return;


	bool first = true;
	os << ",chld={";
	for (auto& pr : _cld)
	{
		if (first) first = false;
		else os << ", ";

		pr.second.show(os);
	}

	os << "}";
}